/*
 * @lc app=leetcode.cn id=611 lang=typescript
 *
 * [611] 有效三角形的个数
 */

// @lc code=start
function triangleNumber(nums: number[]): number {
  // 升序排序，这样只需要找到a+b>c的c就可以了
  nums.sort((a, b) => a - b);

  const m = nums.length;
  let ans = 0;
  // 双重枚举a和b
  for (let i = 0; i < m; i++) {
    for (let j = i + 1; j < m; j++) {
      let l = j + 1;
      let r = m - 1;
      // 数组中会有0的出现，将k默认为j的位置，防止异常
      let k = j;
      // 二分在剩下的区间找到c
      while (l <= r) {
        const mid = l + ((r - l) >> 1);
        if (nums[mid] < nums[i] + nums[j]) {
          k = mid;
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      ans += k - j;
    }
  }

  return ans;
}
// @lc code=end
